<?php
/**
 * @category Goatherd
 * @package Goatherd\Commons
 *
 * @author Copyright (c) 2012 Maik Penz <maik@phpkuh.de>
 * @version $Id: Dawg.php 98 2012-04-27 23:37:13Z maik@phpkuh.de $
 *
 * This file is part of Goatherd library.
 *
 * Goatherd library is free software: you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * Goatherd library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with Goatherd library. If not, see <http://www.gnu.org/licenses/>.
 */
namespace Goatherd\Commons\Word;

/**
 * Directed Acyclid Word Graph (http://en.wikipedia.org/wiki/DAWG).
 *
 * @todo unit test
 * @todo study performance draw-back for writable DAGs
 *
 * @package Goatherd\Commons
 * @subpackage Word
 */
class Dawg
extends Trie
{
    /**
     *
     * @todo reconsider/ verify memory and time difference
     * @var integer
     */
    const NODE_ID = 1;

    /**
     *
     * @var boolean
     */
    protected $_writable = true;

    /**
     * (non-PHPdoc)
     * @see Goatherd\Commons\Word.ITrie::add()
     */
    public function add(&$word)
    {
        $this->_writable and parent::add($word);
        return $this;
    }

    /**
     * Compressed dawgs are not writable (yet).
     *
     * @return boolean
     */
    public function isWritable()
    {
        return $this->_writable;
    }

    /**
     * Calculate dawg from trie.
     *
     */
    public function compress()
    {
        $ids = array();
        $this->compressNode($this->_trie, $ids);

        // can not add to compressed graph
        $this->_writable = false;

        return $this;
    }

    /**
     *
     * @param array $node
     * @param array $ids
     */
    public function compressNode(array &$node, array &$ids)
    {
        $children = $this->getChildren($node);
        foreach ($children as $key => &$child) {
            if ($child !== true) {
                // update ids (as needed)
                // TODO test performance difference if trie is used to store ids
                $id = $this->getNodeId($child);
                if (!isset($ids[$id])) {
                    $ids[$id] = &$child;
                    unset($child[self::NODE_ID]);
                    // compress sub-tree
                    $this->compressNode($child, $ids);
                }
                // replace node children
                $node[$key] = &$ids[$id];
            }
        }
    }

    /**
     *
     * @param array $node
     * @return string
     */
    public function getNodeId(array &$node)
    {
        if (isset($node[self::NODE_ID])) {
            return $node[self::NODE_ID];
        }

        $id = '[';
        isset($node[self::END_OF_WORD]) and $id .= self::END_OF_WORD;
        $children = $this->getChildren($node);
        ksort($children, SORT_ASC);

        foreach ($children as $k => &$child) {
            $id .= $k;
            $child === true or $id .= $this->getNodeId($child);
        }

        $id .= ']';

        $node[self::NODE_ID] = $id;
        return $id;
    }
}